package ysf.com.difficulty;

/**
 * @author ysf
 * @date 2021/6/12 11:22
 * 给定一个字符串，输出最长得回文字串，回文串指的是正着读和反着读都是一样得字符串
 */
public class FiveDemo {
    public static void main(String[] args) {
        String str = "cbvcddc";
        String str2 = "abc435cba";
        String str3 = "abcc";
        /*boolean flag = isPalindromic(str);
        System.out.println(flag);
        String result = longestPalindrome(str);
        System.out.println(result);*/

        /*String results = longestPalindromes(str3);
        System.out.println(results);*/


    }

    //  暴力解法
    public static boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            char leftc = s.charAt(i);
            char rightc = s.charAt(len - i - 1);
            if (leftc != rightc) {
                return false;
            }
        }
        return true;
    }

    public static String longestPalindrome(String s) {
        String ans = "";  // 目标字符串
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        }
        return ans;
    }

    // 解法二求公共字串
    public static String longestPalindromes(String str) {
        if (str.equals("")) return "";
        String origin = str;
        String reverse = new StringBuffer(str).reverse().toString();    // 字符串倒置
        int length = str.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                char leftc = origin.charAt(i);
                char rightc = reverse.charAt(j);
                if (leftc == rightc) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
                    int beforeRev = length - 1 - j;
                    if (beforeRev + arr[i][j] - 1 == i) {
                        maxLen = arr[i][j];
                        maxEnd = i;      // 以i位置结尾得字符串
                    }
                }
            }
        }
        int start = maxEnd - maxLen + 1;
        int end = maxEnd + 1;
        return str.substring(start, end);
    }

    /**
     * personal
     *
     * @return
     */
    public void getResult() {
        String str = "abcddc";
        int length = str.length();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {


            }
        }
    }





}
